package LinkedList;

//表示一个链表节点
//对于节点这个类来说,本身功能单一,比较简单
//如果搞一些get,set方法,后续代码会显得很难看
class Node{
    //节点保存的值
    public String value;
    //节点的下一个元素
    public Node next;
    public Node(String value){
        this.value = value;//初始化新节点的值
        this.next=null;//初始化新节点的下一个元素为null
    }
}
public class MyLinkedList {
    //把链表的头节点表示出来,这样整个链表就能获取到了\
    //此处不包含傀儡节点,所以head==null表示链表为空
    private Node head=null;
    //不像顺序表,许哟啊使用size之类的表示"有效元素"的区间
    //链表不需要,如果搞一个size记录个数,也是可以的,不记录,通过其他方式获取也行

    //插入元素
    //1.尾插
    public void addLast(String value){
        if(head==null){
            //直接让head指向新节点即可
            Node newNode=new Node(value);
            head=newNode;
            return;
        }
        //先找到尾巴,把新的节点,加到尾巴后面
        Node tail=head;//相当于int i=0来理解
        for(tail=head;tail!=null;tail=tail.next){
            if(tail.next==null){
                break;
            }
        }
//通过上述循环,循环结束后,tail就是指向链表的尾巴了
//创建新的节点
        Node newNode = new Node(value);
        //让尾节点的next指向新节点即可
        tail.next=newNode;
        //让新节点的next指向null(由于构造方法中,已经做了这个事情,此处代码不写也行,见Node类中)
        newNode.next=null;

    }
    //2.头插
    public void addFirst(String value){
        //直接就能操作
        //根据刚才的value的值,创建节点
        Node newNode = new Node(value);
        //把型的节点放到头的位置上
        //1.让新节点next指向原来的头节点
        newNode.next = head;
        //2.让hed指向新节点
        head=newNode;
    }
public int size(){
        int size=0;
        for(Node cur=head;cur!=null;cur=cur.next){
            size++;
        }
        return size;
}
    //3.指定位置插入
    public void add(int index,String value){
        //1.先判断index是否合法
        //index==size的时候,表示尾插,也是合法的情况,不需要抛出异常
        if(index<0||index>size()){
            throw new RuntimeException("下标超出范围");
        }
        //2.针对头插的特殊处理
        if(index==0){//因为,index=0时,index-1=-1,循环无法进行所以需要特殊处理
            addFirst(value);
            return;
        }
        //3.根据当前value值,创建新节点
        Node newNode = new Node(value);
        //4.找到index要插入的位置的前一个节点
        //由于当前的链表是"单向链表",每个节点,只能找到next.
        //插入新节点,需要修改前一个节点的next值
        //前一个节点的下标,应该就是index-1
        Node prev=head;
        for(int i=0;i<index-1;i++){
            prev=prev.next;
        }
        //5.通过上述循环,就让prev指向index-1的位置.
        newNode.next=prev.next;
        prev.next=newNode;

    }
    //判定某个元素是否在链表中包含
    public boolean contains(String value){
         for(Node cur=head;cur!=null;cur=cur.next){
             //注意,此处的value是String 的比骄傲,应该用equals方法
             if(cur.value.equals(value)){
                 return true;
             }
         }
         //整个循环结束了,才return false
        return false;
    }
public int indexOf(String value){
        int index=0;
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.value.equals(value)){
                return index;
            }
            index++;
        }
        //通过上述循环,如果不能找到值相同的元素,没触发上述的return index,则返回-1,表示未找到
    return -1;
}
//按照下标来删除元素
    public void remove(int index){
        //先判断index是否合法
        if(index<0||index>=size()){
            throw new RuntimeException("下标超出范围");
        }
        //1.特殊处理index=0的情况
        if(index==0){
            head=head.next;
            return;
        }
        //2.找到被删除元素的前一个结点位置
        Node prev=head;
        for(int i=0;i<index-1;i++){
            prev=prev.next;
        }
        //3.循环结束,prev指向待删除元素的前一个位置
        Node toRemove=prev.next;//待删除元素的位置
        //4.进行删除操作
        prev.next=toRemove.next;

    }
    //按照值来删除
    public void remove(String value){
        //1.如果要删除的元素是head
        if(head.value.equals(value)){
            head=head.next;
            return;
        }
        //2.根据value的值,找到带删除元素的前一个位置
        Node prev=head;
        for(Node cur = head.next;cur!=null;cur=cur.next){
            if(prev.next!=null&&prev.next.value.equals(value)){
                break;
            }
        }
        //3.通过上述循环,prev就指向待删除的前一个位置
        //注意:上述循环的结束可能有两种情况
        //1)value值找到匹配的了
        //2)链表遍历完了,也没找到
        if(prev==null){
            //没找到,直接返回
            return;
        }
        //4.真正进行删除操作
        Node toRemove=prev.next;
        prev.next=toRemove.next;
    }
    //清空链表的所有元素
    public void clear(){
        //直接修改head,head原来指向的所有Node对象都没有引用指向了,都会被释放掉
        head=null;
    }
    @Override
    public String toString(){
        //通过这个方法,遍历链表,构成一个字符串
        //遍历的时候,需要从头节点开始,进行一个一个元素的打印
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(Node cur = head;cur!=null;cur=cur.next){
            stringBuilder.append(cur.value);
            //当前希望最后一个元素后面不加,需要判定当前元素是否是最后一个元素
           //在链表中,最后一个元素的next是null
           if(cur.next!=null){
               stringBuilder.append(",");
           }
        }

        stringBuilder.append("]");
        return stringBuilder.toString();
    }


private static void test1(){//头插示例
        MyLinkedList list = new MyLinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");

        //需要遍历链表并打印元素
    System.out.println(list);
}
private static void test2(){//尾插实例
        MyLinkedList list =new MyLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
    System.out.println(list);
}
    private static void test3(){//指定下标插入实例
        MyLinkedList list =new MyLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.add(0,"x");
        System.out.println(list);
    }
    private static void test4(){//遍历链表,找相同值
        MyLinkedList list =new MyLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list.contains("d"));
        System.out.println(list.contains("x"));
        System.out.println(list.indexOf("c"));//返回的是下标
        System.out.println(list.indexOf("x"));
    }
    private static void test5(){//删除
        MyLinkedList list =new MyLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.remove(1);//对链表的结构的改变,需要先调用方法,再打印链表
        System.out.println(list);
        list.remove("c");
        System.out.println(list);
    }
    private static void test6() {//清空链表
        MyLinkedList list = new MyLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        System.out.println(list);
        list.clear();
        System.out.println(list);
    }
    public static void main(String[] args) {
        //test1();//头插
        //test2();//尾插
        //test3();//按照下标插入
        //test4();//循环链表,找到是否有相同的值
        //test5();//按照下标删除,和指定值删除
        test6();//清空链表
    }
}
